package leetcode;

import leetcode.util.ListNode;
import leetcode.util.TreeNode;

/**
 * Created by tiang on 2018/9/7.
 *
 */
public class ToBST {
    /**
     * 将一个有序列表转换成一个平衡二叉搜索树
     * @param head 链表头结点
     * @return BST
     */
    public TreeNode sortedListToBST(ListNode head) {
        // 如果头结点为空，则返回空
        if(head == null)
            return null;
        // 一个快速指针，一个慢速指针，用来定位链表中心位置
        ListNode dp = head, p = head;
        // 指向链表中心位置的前一个元素
        ListNode pre = null;
        while(dp!=null){
            dp = dp.next;
            if(dp == null)
                break;
            dp = dp.next;
            pre = p;
            p = p.next;
        }
        // 创建根节点
        TreeNode root = new TreeNode(p.val);
        // 将链表分为两段
        if(pre!=null)
            pre.next = null;
        // 如果pre为null，说明当前节点已经为头结点了，那么左节点为null
        root.left = sortedListToBST(pre == null ? null : head);
        // 右子树为下一个节点构成的二叉树
        root.right = sortedListToBST(p.next);
        return root;
    }

    /**
     * 由前序遍历和中序遍历构建一棵树
     * @param preorder 前序遍历
     * @param inorder 中序遍历
     * @return 树根
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0)
            return null;
        if(preorder.length == 1)
            return new TreeNode(preorder[0]);
        int rv = preorder[0];
        TreeNode root = new TreeNode(rv);
        int i=0;
        for(;i<inorder.length;i++){
            if(inorder[i] == rv)
                break;
        }
        int[] leftin = new int[i],
                rightin = new int[inorder.length-i-1];
        System.arraycopy(inorder, 0, leftin, 0, leftin.length);
        System.arraycopy(inorder, i+1, rightin, 0, rightin.length);
        int[] leftPre = new int[i],
                rightPre = new int[inorder.length-i-1];
        System.arraycopy(preorder, 1, leftPre, 0, leftPre.length);
        System.arraycopy(preorder, 1+leftPre.length, rightPre, 0, rightPre.length);
        root.left = buildTree(leftPre, leftin);
        root.right = buildTree(rightPre, rightin);
        return root;
    }
}
